package 牛客算法篇;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * Created with IntelliJ IEDA.
 * Description:
 * User:86186
 * Date:2024-03-13
 * Time:17:47
 */

/**
 *
 牛客算法篇:BM55 没有重复项数字的全排列(回溯)
 描述
 给出一组数字，返回该组数字的所有排列
 例如：
 [1,2,3]的所有排列如下
 [1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2], [3,2,1].
 （以数字在数组中的位置靠前为优先级，按字典序排列输出。）
 数据范围：数字个数 0<n≤60<n≤6
 要求：空间复杂度 O(n!)O(n!) ，时间复杂度 O(n!）O(n!）
 示例1
 输入：
 [1,2,3]
 返回值：
 [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
 */
public class permute {
    public static void main(String[] args) {
        System.out.println(permute(new int[]{1, 2, 3}));
    }
    static List<Integer> list = new ArrayList<>();
    static ArrayList<ArrayList<Integer>> result = new ArrayList<>();
    public static ArrayList<ArrayList<Integer>> permute(int[] num) {
        Arrays.sort(num);
        dfs(num,list);
        return result;
    }

    private static void dfs(int[] num, List<Integer> list){
        if(list.size() == num.length){
            result.add(new ArrayList<>(list));
            return;
        }
        for(int i = 0; i < num.length; i ++){
            if(list.contains(num[i])){
                continue;
            }
            list.add(num[i]);
            dfs(num,list);

            list.remove(list.size() - 1);
        }

    }
}
